home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 11775 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.7 KB
  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: "Best fit" algorithm (help)
  5. Date: 26 Mar 1996 07:21:09 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4j9215INNgbo@keats.ugrad.cs.ubc.ca>
  8. References: <APC&7'0'22b6b83'874@peg.apc.org>
  9. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  10.  
  11. In article <APC&7'0'22b6b83'874@peg.apc.org>,  <riox@peg.apc.org> wrote:
  12.  >Hello,
  13.  >Can anyone  help me?
  14.  >I am looking for a "best fit" algorithm. 
  15.  >The problem I have is very similar to finding the best way of fitting the 
  16.  >maximum number of songs on (say) 45 minute tape.
  17.  
  18. This is loosely related to the ``knapsack problem''.  The knapsack problem is
  19. one of choosing numbers from a given set such that they add up to a particular
  20. number. This is an NP-complete problem to solve in general, but easy for
  21. special cases. Some encryption techniques known as ``knapsack ciphers'' rely on
  22. the difficulty of solving the knapsack problem.
  23.  
  24. Your problem is different, because the selected set of songs don't have to
  25. cover the tape precisely.
  26.  
  27.  >If one knows the length of each song and the number of songs, how can one 
  28.  >find the best arrangement to occupy maximum amount of tape without "cutting"
  29.  >off any songs. Ie, how to minimise the empty space left on the tape.
  30.  >
  31.  >Can you help?
  32.  
  33. Assuming that you don't care _which_ songs go on the tape, try a ``greedy''
  34. approach. Always add to the tape a song which will leave the most free space.
  35. This means starting with the smallest one, and adding the next bigger one and
  36. so on. This should yield an optimal solution for the constraint of maximizing
  37. the number of songs that go on the tape. It won't minimize the left-over space,
  38. however.
  39.  
  40. The goals of maximizing the number of songs and minimizing left over space are
  41. quite divergent. Once could minimize the space with just a few songs, or by
  42. fitting the provable maximum number of songs possible one could end up with a
  43. large waste. For example, if you have 37 songs that are 1 minute each, and one
  44. song that is ten minutes long, the greatest number you can fit is 37, but you
  45. waste 8 minutes of the tape.  You can take two songs out and put in the ten
  46. minute song to end up with no waste, but only 36 songs.
  47.  
  48. To solve the problem, you have to define a heuristic function: a way of
  49. determining whether a solution is good, or whether one solution is better than
  50. another. You can then search the large tree of possibilities until you find
  51. something that is good enough.
  52.  
  53. In any case, these sorts of problems are typically covered in books about
  54. algorithm analysis. No hastily produced Usenet posting can supplant the insight
  55. offered by a well researched paper or textbook.
  56. -- 
  57.  
  58.